#! -*- encoding=utf-88 -*-
from computer_sience import DoubleLinkList, Node


class FIFOCache(object):
    def __init__(self, capacity):  # capacity 当前缓冲最大能够容纳的容量
        self.capacity = capacity
        self.size = 0
        self.map = {}  # 保存key和node之间的关系
        self.list = DoubleLinkList(self.capacity)

    # 读取缓冲中的某个结点
    def get(self, key):
        if key not in self.map:
            return -1
        else:
            node = self.map.get(key)
            return node.value

    # 往缓冲里添加结点
    def put(self, key, value):
        # 判断内存是否已经满了
        if self.capacity == 0 :
            return
        # 如果key在本地的map中
        if key in self.map:
            node = self.map.get(key)
            self.list.remove(node)
            node.value = value
            self.list.append(node)
        else:
            # 容量已经满了，淘汰掉最先进入缓冲的节点
            if self.size == self.capacity:
                node = self.list.pop()
                del self.map[node.key]
                self.size -= 1
            node = Node(key, value)
            self.list.append(node)
            self.map[key] = node
            self.size += 1

    def print(self):
        self.list.print()


if __name__ == '__main__':
    cache = FIFOCache(2)
    cache.put(1, 1)
    cache.print()
    cache.put(2, 2)
    cache.print()
    print(cache.get(1))
    cache.put(3, 3)
    cache.print()
    print(cache.get(3))
    cache.put(4, 4)
    cache.print()
    print(cache.get(2))

